package leetcode.nTree;

import datastructure.tree.Node;

import java.util.*;

/**
 * @Description: https://leetcode.cn/problems/n-ary-tree-postorder-traversal/
 * 给定一个 n 叉树的根节点 root，返回 其节点值的 后序遍历 。
 *
 * n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
 *
 * 草稿(旧)：5
 *
 * @Author Ammar
 * @Create 2023/3/30 21:47
 */
public class _590_N叉树的后序遍历 {

    /**
     * 递归
     * @param
     */
    public static List<Integer> postorder1(Node root) {
        List<Integer> list = new LinkedList<>();
        if (root == null) return list;
        if (root.children == null || root.children.size() == 0) {
            list.add(root.val);
            return list;
        }
        for (int i = 0; i < root.children.size(); i++) {
            list.addAll(postorder1(root.children.get(i)));
        }
        list.add(root.val);
        return list;
    }

    /**
     * 根据后序反转数组，然后根据数组构建入栈顺序
     * @param
     */
    public static List<Integer> postorder(Node root) {
        List<Integer> list = new LinkedList<>();
        if (root == null) return list;
        Deque<Node> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            list.add(node.val);
            if (node.children != null && node.children.size() != 0) {
                for (int i = 0; i < node.children.size(); i++) {
                    stack.push(node.children.get(i));
                }
            }
        }
        Collections.reverse(list);
        return list;
    }
}
